package com.stefan.tree;

import com.stefan.queue.StefanQueue;

//二叉查找树/二叉排序树
//这里用已有的TreeNode来实现，只需要这个类里面有个root TreeNode
//还有一种实现就是这个类本上就是一个Tree
//为了简化这里直接用Integer，真实的场景是所有Integer的地方要改成E，然后E是可排序的即实现排序接口
public class BinarySearchStefanTree<E> implements StefanTree<E> {
    private TreeNode<Integer> root; //这里就用Integer的TreeNode把，如果用一个DTO那这个DTO要实现排序接口的
    private int size; //树的size
    public BinarySearchStefanTree () {
        root = null;
        size = 0;
    }
    //二分查找树是如何插入一个元素的
    public void insert (Integer data) {
        //创建一个TreeNode
        TreeNode<Integer> treeNode = new TreeNode<>(data);
        if (root == null) {
            root = treeNode;
            size++;
        } else {
            put(data,root);
        }
    }
    public void put(Integer data,TreeNode<Integer> treeNode) {
        TreeNode<Integer> lof; //左子树还是右子树？
        if (data > treeNode.getData()) {//如果data大于节点的data就放右边树
            lof = treeNode.getRight();
            if (lof == null) {
                treeNode.setRight(new TreeNode<>(data)); //如果右边树是空，就用data创建一个treeNode放入
                size++;
                return;
            }
        } else {
            //节点放左边树
            lof = treeNode.getLeft();
            if (lof == null) {
                treeNode.setLeft(new TreeNode<>(data)); //如果左边树是空，就用data创建一个treeNode放入
                size++;
                return;
            }
        }
        //上面的情况，就是左边子树或者右边子树不等于null就递归 - 重复这样做
        //一直找到左边或者右边子树为null的情况 - 说明是叶子几点
        put(data,lof);
    }

    public TreeNode<Integer> getRoot() {
        return root;
    }

    public void setRoot(TreeNode<Integer> root) {
        this.root = root;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    public static void main(String[] args) {
        BinarySearchStefanTree<Integer> binarySearchStefanTree = new BinarySearchStefanTree<>();
        binarySearchStefanTree.insert(8);
        binarySearchStefanTree.insert(9);
        binarySearchStefanTree.insert(10);
        binarySearchStefanTree.insert(5);
        binarySearchStefanTree.insert(7);
        binarySearchStefanTree.insert(4);
        binarySearchStefanTree.insert(2);
        binarySearchStefanTree.mid(binarySearchStefanTree.getRoot());
    }
}
